/** processor.cpp
  * tomasulo pipelined processor
  * Author: Long Tran
  * Email:  ltran3@gatech.edu
  * Date created: Mar 19 2011
  */

#include <sstream>
#include <algorithm>
#include <iomanip>
#include "processor.h"

int global_time = 0;

Processor::Processor(std::istream& input, int k0, int k1, int k2, int D, int m, int N, int verbose)
  : input_(input),
    k0_(k0), k1_(k1), k2_(k2), D_(D), m_(m), N_(N),
    regFile_(verbose),
    dpQ_(program_, D, verbose),                                  // prepare dispatch queue
    verbose_(verbose)
{
  for (int i = 0; i < 128; i++)
    regFile_.push_back(Register(i));                    // prepare 128 registers
  for (int k = 0; k < k0; k++)
    fu_.push_back(FunctionUnit(program_, 0, 1, verbose));        // prepare (k0, k1, k2) funtion units
  for (int k = 0; k < k1; k++)
    fu_.push_back(FunctionUnit(program_, 1, 2, verbose));
  for (int k = 0; k < k2; k++)
    fu_.push_back(FunctionUnit(program_, 2, 3, verbose));
  shQ_.push_back(SchedQ(program_, regFile_, 0, m*k0, verbose));  // prepare 3 scheduling queues
  shQ_.push_back(SchedQ(program_, regFile_, 1, m*k1, verbose));
  shQ_.push_back(SchedQ(program_, regFile_, 2, m*k2, verbose));
}

int Processor::infiniteLoop()
{
  bool ok = true;
  change_ = true;
//  dpQ_.fetch(input_, N_);        // first cycle should only have IF/ID
  global_time = 0;
  while (ok /*&& change_*/) {
    // init a cycle
    dpQ_.markEmptySlots();
    for (int type = 0; type < 3; type++) shQ_[type].markEmptySlots();
    clearOldCDB();

    // stages
    change_ = false;
    if (dpQ_.fetch(input_, N_))  // instruction fetch
      change_ = true;
    updateRegs();
    dispatch();                  // reserved slots
    fire();
    execute();                   // execute function units
    updateSchedQ();
    stateUpdate();

//    if (!change_) break;

    dump();

    if (verbose_ > 1) {
      std::string line;
      std::getline(std::cin, line);
    }

    global_time++;               // next cycle

    // check if done all instructions
    ok = false;
    if (!input_.eof()) ok = true;
    for (uint i = 0; i < dpQ_.size() && !ok; i++)
      if (!dpQ_.isEmpty(i)) { ok = true; }
    for (int type = 0; type < 3 && !ok; type++)
      for (uint rs = 0; rs < shQ_[type].size() && !ok; rs++)
        if (!shQ_[type].isEmpty(rs)) { ok = true; }
  }
  program_.output();
  return 0;
}

void Processor::updateRegs()
{
  if (verbose_) std::cerr << std::dec << global_time << " --- update regFile --- \n";
  for (uint i = 0; i < cdb_.size(); i++) {
    change_ = true; if (verbose_) std::cerr << "change 1\n";
    int tag = cdb_[i].tag_;
    int reg = cdb_[i].reg_;
    int time = cdb_[i].time_;
    if (verbose_) std::cerr << "reg update reg = " << std::dec << reg << " tag = " << tag << " time = " << time << "\n";
    if (time <= global_time && reg >= 0) regFile_[reg].ready(tag);
  }
}

struct SchedEntry {
  int tag_, type_, rs_;
  SchedEntry() {}
  SchedEntry(int tag, int type, int rs) : tag_(tag), type_(type), rs_(rs) {}
  bool operator()(const SchedEntry& e1, const SchedEntry& e2) const {
    return e1.tag_ < e2.tag_;
  }
};

void Processor::fire()
{
  if (verbose_) std::cerr << std::dec << global_time << " --- fire --- \n";
  std::vector<SchedEntry> entries;
  for (int type = 0; type < 3; type++) {
    for (uint rs = 0; rs < shQ_[type].size(); rs++) if (!shQ_[type].isEmpty(rs)) {
      const Instruction& inst = shQ_[type].inst(rs);
      if (inst.scheduleTime_ <= global_time && inst.executeTime_ == -1 &&
          inst.src1Ready_ && inst.src2Ready_) { // not fired, independent
        if (verbose_) std::cerr << std::dec << global_time << " considering tag = " << inst.tag() << "\n";
        entries.push_back(SchedEntry(inst.tag(), type, rs));
      }
    }
  }
  std::sort(entries.begin(), entries.end(), SchedEntry());

  for (uint i = 0; i < entries.size(); i++) {
    int type = entries[i].type_;
    int rs = entries[i].rs_;
    int id = shQ_[type][rs];
    const Instruction& inst = shQ_[type].inst(rs);
    if (verbose_) std::cerr << std::dec << global_time << " try to fire tag = " << inst.tag() << "\n";
    for (uint k = 0; k < fu_.size(); k++) if (fu_[k].type() == type) {
      bool success = fu_[k].fire(id);
      if (success) {                      // successfully fired, instruction stays in schedQ until completed
        change_ = true; if (verbose_) std::cerr << "change 2\n";
        break;
      }
    }
  }
}

struct DispatchEntry {
  int tag_, slot_;
  DispatchEntry() {}
  DispatchEntry(int tag, int slot) : tag_(tag), slot_(slot) {}
  bool operator()(const DispatchEntry& e1, const DispatchEntry& e2) const {
    return e1.tag_ < e2.tag_;
  }
};

void Processor::dispatch()
{
  if (verbose_) std::cerr << std::dec << global_time << " --- dispatch --- \n";
  std::vector<DispatchEntry> entries;
  for (uint i = 0; i < dpQ_.size(); i++) if (!dpQ_.isEmpty(i)) {
    const Instruction& inst = dpQ_.inst(i);
    if (inst.dispatchTime_ <= global_time)
      entries.push_back(DispatchEntry(inst.tag(),i));
  }
  std::sort(entries.begin(), entries.end(), DispatchEntry());

  for (uint i = 0; i < entries.size(); i++) {
    int slot = entries[i].slot_;
    int id = dpQ_[slot];
    bool success = shQ_[dpQ_.inst(slot).type()].dispatch(id);
    if (success) {
      dpQ_.clearSlot(slot);
      change_ = true; if (verbose_) std::cerr << "change 3\n";
    }
  }
}

void Processor::execute()
{
  if (verbose_) std::cerr << std::dec << global_time << " --- execute --- \n";
  for (uint k = 0; k < fu_.size(); k++) if (!fu_[k].empty()) {
    int id = fu_[k].front();
    Instruction& inst = program_[id];
    if (inst.executeTime_ > global_time) continue;
    int type = fu_[k].type();
    int cycle = fu_[k].cycle();
    if (type == 0 || (type > 0 && inst.executeTime_ + cycle - 1 <= global_time)) {   // check if instruction's execution is done
      fu_[k].pop(); // remove from excution pipeline
      cdb_.push_back(CDB(inst.tag(), inst.dest(), global_time+1)); // put result to CDB, available next cycle
      inst.updateTime_ = global_time+1; // state update in next cycle
      if (verbose_) std::cerr << std::dec << global_time
                << " execute done tag = " << inst.tag() << "\n";
      change_ = true; if (verbose_) std::cerr << "change 7\n";
    }
  }
}

void Processor::updateSchedQ()
{
  if (verbose_) std::cerr << std::dec << global_time << " --- update schedQ --- \n";
  for (uint i = 0; i < cdb_.size(); i++)
  {
    int tag = cdb_[i].tag_;
    int time = cdb_[i].time_;
    if (global_time < time) continue;
    for (int type = 0; type < 3; type++)
      for (uint rs = 0; rs < shQ_[type].size(); rs++)
        shQ_[type].update(rs, tag);
    change_ = true; if (verbose_) std::cerr << "change 4\n";
  }
}

void Processor::clearOldCDB() {
  std::vector<CDB> tmp = cdb_;
  cdb_.clear(); // keep only new result buses
  for (uint i = 0; i < tmp.size(); i++) if (tmp[i].time_ >= global_time)
    cdb_.push_back(tmp[i]);
}

void Processor::stateUpdate()
{
  if (verbose_) std::cerr << std::dec << global_time << " --- state update --- \n";
  for (int type = 0; type < 3; type++) {
    for (uint rs = 0; rs < shQ_[type].size(); rs++) if (!shQ_[type].isEmpty(rs)) {
      Instruction& inst = shQ_[type].instRef(rs);
      if (inst.updateTime_ >= 0 && inst.updateTime_ <= global_time) {
        shQ_[type].clearSlot(rs);
        if (verbose_) std::cerr << std::dec << global_time
                  << " clear RS tag = " << inst.tag() << " ***!!!\%\%\%\n";
        change_ = true; if (verbose_) std::cerr << "change 5\n";
      }
    }
  }
}

void Processor::dump()
{
  std::cerr << "----- " << std::dec << global_time << " processor dump *****\n";
  std::cerr << "++dispQ " << "\n";
  dpQ_.dump();
  for (int type = 0; type < 3; type++) {
    std::cerr << "--schedQ " << type << "\n";
    shQ_[type].dump();
  }
  std::cerr.flush();
}

// ====================== Instruction ====================

int Instruction::currentTag_ = 0;

void Instruction::read(std::istream &input)
{
  std::string line;
  std::getline(input, line);
  if (line.empty()) {
    type_ = -1; // no more instruction from input
    return;
  }
  std::stringstream s(line);
  tag_ = currentTag_++;
  s >> std::hex >> addr_ >> std::dec >> type_ >> dest_ >> src1_ >> src2_;
  fetchTime_ = global_time;
  dispatchTime_ = global_time+1;
//  std::cerr << std::dec << global_time
//            << " fetch " << std::dec << tag_ << " "
//            << std::hex << addr_ << " "
//            << std::dec << type_ << " "
//            << dest_ << " "
//            << src1_ << " "
//            << src2_ << "\n";
}

// ====================== DispatchQ ====================

bool DispatchQ::fetch(std::istream &input, int N)
{
  if (verbose_) std::cerr << std::dec << global_time << " --- fetch --- \n";
  bool ret = false;
  for (int i = 0; i < N && !emptySlot_.empty(); i++) {
    int id = program_->getNext(input);
    int j = emptySlot_.front();
    if (id != -1) {
      this->at(j) = id;
      empty_[j] = false;
      emptySlot_.pop();
      ret = true;
      if (verbose_) std::cerr << "change 6\n";
    }
  }
  return ret;
}

//void DispatchQ::sort()
//{
//  for (int i = 0; i < size_; i++) {
//    for (int j = i+1; j < size_; j++) if (empty_[j] || (!empty_[i] && inst(i).tag() > inst(j).tag())) {
//      int tmp = this->at(i); this->at(i) = this->at(j); this->at(j) = tmp;
//      bool b_tmp = empty_[i]; empty_[i] = empty_[j]; empty_[j] = b_tmp;
//    }
//  }
//}

void DispatchQ::dump()
{
  for (uint i = 0; i < size(); i++) {
    std::cerr << "[" << std::dec << i << "] = ";
    if (isEmpty(i)) {
      std::cerr << "empty";
    }
    else {
      std::cerr << inst(i).tag() << " time = " << inst(i).fetchTime_;
    }
    std::cerr << "\n";
  }
}

// ======================= SchedQ ======================

bool SchedQ::dispatch(int i)
{
  Instruction& inst = program_->at(i);
  if (global_time < inst.dispatchTime_) return false;
  if (emptySlot_.empty()) return false;
  int slot = emptySlot_.front(); emptySlot_.pop();

  this->at(slot) = i;
  this->empty_[slot] = false;
  inst.scheduleTime_ = global_time+1;
  regFile_->processTag(inst);
  if (verbose_) std::cerr << std::dec << global_time
            << " dispatch tag = " << inst.tag() << "\n";
  return true;
}

void SchedQ::update(int rs, int tag)
{
  if (isEmpty(rs)) return;
  Instruction& inst = instRef(rs);
  if (!inst.src1Ready_ && inst.src1Tag_ == tag) {
    inst.src1Ready_ = true;
    if (verbose_) std::cerr << std::dec << global_time
        << " update src1 tag = " << std::dec << inst.tag() << "\n";
  }
  if (!inst.src2Ready_ && inst.src2Tag_ == tag) {
    inst.src2Ready_ = true;
    if (verbose_) std::cerr << std::dec << global_time
        << " update src2 tag = " << std::dec << inst.tag() << "\n";
  }
}

void SchedQ::dump()
{
  for (uint i = 0; i < size(); i++) {
    std::cerr << "[" << std::dec << i << "] = ";
    if (isEmpty(i)) std::cerr << "empty";
    else {
      std::cerr << inst(i).tag() << " sched time = " << inst(i).scheduleTime_
                << " type=" << inst(i).type()
                << " src1=[" << inst(i).src1() << " " << inst(i).src1Ready_ << " " << inst(i).src1Tag_ << "]"
                << " src2=[" << inst(i).src2() << " " << inst(i).src2Ready_ << " " << inst(i).src2Tag_ << "]"
                << " dest=[" << inst(i).dest() << " " << inst(i).tag() << "]"
                << " " << (inst(i).executeTime_ != -1 ? (inst(i).updateTime_ != -1 ? "exec done":"executing") : "---------");
    }
    std::cerr << "\n";
  }
}

// ======================= RegisterFile ================

void RegisterFile::processTag(Instruction &inst)
{
  if (verbose_) std::cerr << std::dec << global_time
      << " check regfile dest = " << std::dec << inst.dest() << " "
      << " src1 = " << inst.src1() << " src2 = " << inst.src2() << "\n";
  // check src1
  if (inst.src1() == -1 || this->at(inst.src1()).isReady()) {
    inst.src1Ready_ = true;
  }
  else {
    inst.src1Ready_ = false;
    inst.src1Tag_ = this->at(inst.src1()).tag();
  }

  // check src2
  if (inst.src2() == -1 || this->at(inst.src2()).isReady()) {
    inst.src2Ready_ = true;
  }
  else {
    inst.src2Ready_ = false;
    inst.src2Tag_ = this->at(inst.src2()).tag();
  }

  // set DestReg.tag
  if (inst.dest() != -1)
    this->at(inst.dest()).newTag(inst.tag());
}

// ================== Function Unit =====================

bool FunctionUnit::fire(int id)
{
  Instruction& inst = program_->at(id);
  if (global_time < inst.scheduleTime_) return false;
  if (empty() || (type_ > 0 && program_->at(this->back()).executeTime_ <= global_time)) {
    inst.executeTime_ = global_time+1;
    this->push(id);
    if (verbose_) std::cerr << std::dec << global_time
        << " fire tag = " << std::dec << inst.tag() << " addr = " << std::hex << inst.addr() << "\n";
    return true;
  }
  return false;
}

// =================== Output ========================
void Program::output()
{
  std::cout << "INST	FETCH	DISP	SCHED	EXEC	STATE\n";
  for (uint i = 0; i < size(); i++) {
    std::cout << std::left << std::setw(8) << at(i).tag()
              << std::left << std::setw(8) << at(i).fetchTime_
              << std::left << std::setw(8) << at(i).dispatchTime_
              << std::left << std::setw(8) << at(i).scheduleTime_
              << std::left << std::setw(8) << at(i).executeTime_
              << std::left << std::setw(8) << at(i).updateTime_ << "\n";
  }
}
